package com.example.demo.sort;


import cn.hutool.log.Log;

import java.util.Arrays;
import java.util.function.Function;

/**
 * <pre>
 * 描述: 排序算法
 * </pre>
 *
 * @author godelgnis(wujiaer)
 * @version 1.0.0
 * @date 2021/12/9 19:53
 */
public class SortAlgorithmTest {
    private static Log log = Log.get();


    private static int[] array = { 13, 17, 4, 2, 8, 12, 12, 13, 19, 18, 5, 9, 13, 0, 4, 17, 18, 18, 18, 5, 19, 19, 12, 4, 5, 3, 9, 8, 12, 10 };

    private static int[] answer = { 0, 2, 3, 4, 4, 4, 5, 5, 5, 8, 8, 9, 9, 10, 12, 12, 12, 12, 13, 13, 13, 17, 17, 18, 18, 18, 18, 19, 19, 19 };

    public static void main(String[] args) {
        SortAlgorithmTest.calculate(SortType.Bubble);
        SortAlgorithmTest.calculate(SortType.SimpleSelect);
        SortAlgorithmTest.calculate(SortType.SimpleInsert);
        SortAlgorithmTest.calculate(SortType.Shell);
        SortAlgorithmTest.calculate(SortType.Merge);
        SortAlgorithmTest.calculate(SortType.MergePlus);
        SortAlgorithmTest.calculate(SortType.Quick);
        SortAlgorithmTest.calculate(SortType.Heap);
        SortAlgorithmTest.calculate(SortType.Count);
        SortAlgorithmTest.calculate(SortType.Bucket);
        SortAlgorithmTest.calculate(SortType.Radix);
        SortAlgorithmTest.calculate(SortType.JdkSort);
    }

    public static void calculate(SortType sortType) {
        calculate(sortType, array, answer);
    }

    public static void calculate(SortType sortType, int[] sourceArray, int[] answerArray) {
        log.info(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>");
        log.info("name: {}", sortType.name());
        calculate(sortType.function, sourceArray, answerArray);
        log.info("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<");
    }

    public static void calculate(Function<int[], int[]> function, int[] sourceArray, int[] answerArray) {
        int[] clone = Arrays.copyOf(sourceArray, sourceArray.length);
        long s = System.nanoTime();
        int[] result = function.apply(clone);
        long e = System.nanoTime();
        boolean equals = Arrays.equals(result, answerArray);
        log.info("排序时间: {}ms, 排序结果: {}", (e - s)/1000000.00, equals);
    }

    enum SortType {
        // 排序算法类型
        Bubble(SortAlgorithm::bubble),
        SimpleSelect(SortAlgorithm::simpleSelect),
        SimpleInsert(SortAlgorithm::simpleInsert),
        Shell(SortAlgorithm::shell),
        Merge(SortAlgorithm::mergeSort),
        MergePlus(SortAlgorithm::mergeSortPlus),
        Quick(SortAlgorithm::quick),
        Heap(SortAlgorithm::heap),
        Count(SortAlgorithm::count),
        Bucket(SortAlgorithm::bucket),
        Radix(SortAlgorithm::radix),
        JdkSort(SortAlgorithm::jdkSort);

        private Function<int[], int[]> function;

        SortType(Function<int[], int[]> function) {
            this.function = function;
        }
    }

    static class SortAlgorithm {

        static int[] bubble(int[] arr) {
            int length = arr.length;
            for (int i = 0; i < length - 1; i++) {
                for (int j = 0; j < length - 1 - i; j++) {
                    if (arr[j] > arr[j+1]) {
                        int tmp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = tmp;
                    }
                }
            }
            return arr;
        }

        static int[] simpleSelect(int[] arr){
            int len = arr.length;
            for (int i = 0; i < len - 1; i++) {
                int minIndex = i;
                for (int j = i + 1; j < len; j++) {
                    if (arr[j] < arr[minIndex]) {
                        minIndex = j;
                    }
                }
                int tmp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = tmp;
            }
            return arr;
        }

        static int[] simpleInsert(int[] arr) {
            return simpleInsert(arr, arr.length);
        }

        static int[] simpleInsert(int[] arr, int len) {
            for (int i = 1; i < len; i++) {
                int preIndex = i - 1;
                int current = arr[i];
                while (preIndex >= 0 && arr[preIndex] > current) {
                    arr[preIndex + 1] = arr[preIndex];
                    preIndex--;
                }
                arr[preIndex + 1] = current;
            }
            return arr;
        }


        static int[] shell(int[] arr) {
            int len = arr.length;
            for (int step = len / 2; step >= 1; step /= 2) {
                for (int i = step; i < len; i++) {
                    int current = arr[i];
                    int preIndex = i - step;
                    while (preIndex >= 0 && arr[preIndex] > current) {
                        arr[preIndex + step] = arr[preIndex];
                        preIndex -= step;
                    }
                    arr[preIndex + step] = current;
                }
            }
            return arr;
        }


        static int[] mergeSort(int[] arr) {
            if (arr.length < 2) {
                return arr;
            }
            int middle = arr.length / 2;
            int[] left = Arrays.copyOfRange(arr, 0, middle);
            int[] right = Arrays.copyOfRange(arr, middle, arr.length);
            return merge(mergeSort(left), mergeSort(right));
        }

        static int[] merge(int[] left, int[] right) {
            int[] result = new int[left.length + right.length];
            int li = 0;
            int ri = 0;
            int cursor = 0;
            while (li < left.length && ri < right.length) {
                if (left[li] < right[ri]) {
                    result[cursor++] = left[li++];
                }else {
                    result[cursor++] = right[ri++];
                }
            }
            while (li < left.length) {
                result[cursor++] = left[li++];
            }
            while (ri < right.length) {
                result[cursor++] = right[ri++];
            }
            return result;
        }

        static int[] mergeSortPlus(int[] arr) {
            int[] tmp = new int[arr.length];
            mergeSortPlus(arr, 0, arr.length-1, tmp);
            return arr;
        }

        static void mergeSortPlus(int[] arr, int li, int hi, int[] tmp) {
            if (li < hi) {
                int middle = (li + hi) / 2;
                mergeSortPlus(arr, li, middle, tmp);
                mergeSortPlus(arr, middle + 1, hi, tmp);
                mergePlus(arr, li, middle, hi, tmp);
            }
        }

        static void mergePlus(int[] arr, int li, int mid, int hi, int[] tmp) {
            int cursor = 0;
            int i = li;
            int j = mid + 1;
            while (i <= mid && j <= hi) {
                if (arr[i] < arr[j]) {
                    tmp[cursor++] = arr[i++];
                }else {
                    tmp[cursor++] = arr[j++];
                }
            }
            while (i <= mid) {
                tmp[cursor++] = arr[i++];
            }
            while (j <= hi) {
                tmp[cursor++] = arr[j++];
            }
            int t = 0;
            while (li <= hi) {
                arr[li++] = tmp[t++];
            }
        }

        static int[] jdkSort(int[] arr) {
            Arrays.sort(arr);
            return arr;
        }


        static int[] quick(int[] arr) {
            return quickSort(arr, 0, arr.length - 1);
        }

        static int[] quickSort(int[] arr, int left, int right) {
            if (left < right) {
                int pi = partition(arr, left, right);
                quickSort(arr, left, pi - 1);
                quickSort(arr, pi + 1, right);
            }
            return arr;
        }

        static int partition(int[] arr, int left, int right) {
            int pivot = left, index, tmp;
            for (int i = index = pivot + 1; i <= right; i++) {
                if (arr[i] < arr[pivot]) {
                    tmp = arr[i];
                    arr[i] = arr[index];
                    arr[index] = tmp;

                    index++;
                }
            }

            tmp = arr[pivot];
            arr[pivot] = arr[index-1];
            arr[index-1] = tmp;

            return index - 1;
        }

        static int[] heap(int[] arr) {
            int len = arr.length;

            buildHeap(arr, len);

            for (int i = len - 1; i > 0; i--) {
                swap(arr, 0, i);
                len--;
                heapify(arr, 0, len);
            }

            return arr;
        }

        private static void buildHeap(int[] arr, int len) {
            for (int i = len / 2; i >= 0; i--) {
                heapify(arr, i, len);
            }
        }

        private static void heapify(int[] arr, int i, int len) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int maxIndex = i;

            if (left < len && arr[left] > arr[maxIndex]) {
                maxIndex = left;
            }
            if (right < len && arr[right] > arr[maxIndex]) {
                maxIndex = right;
            }
            if (maxIndex != i) {
                swap(arr, i, maxIndex);
                heapify(arr, maxIndex, len);
            }
        }

        private static void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }


        static int[] count(int[] arr) {
            if (arr.length == 0) {
                return arr;
            }
            int maxValue = getMaxValue(arr);
            int[] bucket = new int[maxValue + 1];
            for (int value: arr) {
                bucket[value]++;
            }
            int index = 0;
            for (int j = 0; j < bucket.length; j++) {
                while (bucket[j] > 0) {
                    arr[index++] = j;
                    bucket[j]--;
                }
            }
            return arr;
        }

        static int getMaxValue(int[] arr) {
            int max = arr[0];
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] > max) {
                    max = arr[i];
                }
            }
            return max;
        }


        static int[] bucket(int[] arr) {
            return bucket(arr, 5);
        }

        static int[] bucket(int[] arr, int bucketSize) {
            if (arr.length == 0) {
                return arr;
            }
            int max = arr[0];
            int min = arr[0];
            for (int value : arr) {
                if (value > max) {
                    max = value;
                } else if (value < min) {
                    min = value;
                }
            }
            int bucketCount = (max - min) / bucketSize + 1;
            int[][] buckets = new int[bucketCount][0];

            for (int i = 0; i < arr.length; i++) {
                int index = (arr[i] - min) / bucketSize;
                buckets[index] = append(buckets[index], arr[i]);
            }

            int arrIndex = 0;
            for (int i = 0; i < buckets.length; i++) {
                int[] bucket = buckets[i];
                if (bucket.length <= 0) {
                    continue;
                }
                int[] ints = simpleInsert(bucket);
                for (int value: ints) {
                    arr[arrIndex++] = value;
                }
            }
            return arr;
        }

        static int[] append(int[] arr, int value) {
            int[] appendArr = Arrays.copyOf(arr, arr.length + 1);
            appendArr[appendArr.length - 1] = value;
            return appendArr;
        }

        static int getNumberLen(int value) {
            int len = 0;
            while (value > 0) {
                len++;
                value /= 10;
            }
            return len;
        }

        static int[] radix(int[] arr) {
            int len = arr.length;
            if (len <= 0) {
                return arr;
            }
            int max = getMaxValue(arr);
            int radix = getNumberLen(max);

            int mod = 10;
            int dev = 1;
            for (int i = 0; i < radix; i++, dev *= 10, mod *= 10) {
                int[][] buckets = new int[mod][0];
                for (int value: arr) {
                    int index = (value % mod) / dev;
                    buckets[index] = append(buckets[index], value);
                }
                int pos = 0;
                for (int[] bucket : buckets) {
                    for (int value : bucket) {
                        arr[pos++] = value;
                    }
                }
            }
            return arr;
        }
    }
}